package com.kobeliu.entity;

import java.util.Arrays;

/**
 * 剑指 40
 *
 *
 */

public class Demo_57_sword_40 {

    public static void main(String[] args) {

        int n = 2;
        int i = (n>>2) & 0x1;
        System.out.println(i==1);

        int[] nums = new int[]{3,2,1};
        System.out.println(Arrays.toString(getLeastNumbers(nums, 2)));

    }

    /**
     * 调用API做法 并没有什么意义
     * @param arr
     * @param k
     * @return
     */
    public static int[] getLeastNumbers1(int[] arr, int k) {
        int len = arr.length;
        if(len<k) return new int[]{};
        if(k==0) return new int[]{};
        Arrays.sort(arr);
        int[] temp = new int[k];

        for(int i = 0;i<k;i++){
            temp[i] = arr[i];
        }

        return temp;

    }

    /**
     * 堆排序 小根堆 每次放到nums[0],重复k次
     * @param arr
     * @param k
     * @return
     */
    public static int[] getLeastNumbers(int[] arr, int k) {

        //创建小根堆
        int[] nums = heapInsert(arr);
        int[] temp = new int[k];
        //指到下标
        int len = nums.length;
        int i = 0;

        while(i<k){
            temp[i] = nums[0];
            nums[0] = nums[--len];
            heapify(nums,len);
            i++;
        }
        return temp;

    }

    //初始化小根堆
    static int[] heapInsert(int[] arr){
        int[] nums = new int[arr.length];
        nums[0] = arr[0];
        int k = 0;
        for(int i=1;i<arr.length;i++){
            nums[i] = arr[i];
            k = i;
            while(nums[k] <nums[(k-1)/2]){
                swap(nums,k,(k-1)/2);
                k = (k-1)/2;
            }
        }

        return nums;
    }

    static void heapify(int[] nums,int heapSize){
        int i = 0;
        int num = 0;
        while(i<heapSize){
            if((2*i+1)>heapSize){
                break;
            }
            else if((2*i+2) < heapSize){
                num = nums[2*i+1]<=nums[2*i+2]?2*i+1:2*i+2;
                if(nums[i]>nums[num]){
                    swap(nums,i,num);
                    i = num;
                }else{
                    break;
                }
            }else{
                if(nums[i]>nums[2*i+1]){
                    swap(nums,i,2*i+1);
                    i = 2*i+1;
                }else{
                    break;
                }
            }
        }
    }

    private static void swap(int[] nums1, int i, int j) {
        nums1[i] = nums1[i] ^ nums1[j];
        nums1[j] = nums1[i] ^ nums1[j];
        nums1[i] = nums1[i] ^ nums1[j];
    }
}
